package tree.PathSum;

import tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName HasPathSum
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-16 20:42
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class HasPathSum {

    /**
     * 112. 路径总和
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */

    public boolean hasPathSum(TreeNode root, int target) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null && target == root.val)
            return true;

        return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);
    }

    public boolean hasPathSum1(TreeNode root, int target) {
        if (root == null) return false;
        boolean isFlag = false;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> queueNum = new LinkedList<>();
        queue.add(root);
        queueNum.add(root.val);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode poll = queue.poll();
                Integer num = queueNum.poll();
                if (poll.left == null && poll.right == null && target == num) {
                    return true;
                }
                if (poll.left != null) {
                    queue.add(poll.left);
                    queueNum.add(poll.left.val + num);
                }

                if (poll.right != null) {
                    queue.add(poll.right);
                    queueNum.add(poll.right.val + num);
                }
                size--;
            }
        }
        return false;

    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);

        treeNode.left = treeNode1;
        treeNode.right = treeNode2;
        HasPathSum hasPathSum = new HasPathSum();
//        System.out.println(hasPathSum.hasPathSum1(treeNode, 5));
        boolean b = hasPathSum.hasPathSum1(treeNode, 5);
        System.out.println(b);
    }

//    1
//  2   3
}